package com.leet.competition;

import java.util.*;

public class MinimumEffortPath {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        List<int[]> edges = new LinkedList<>();
        for(int i = 0; i < rows; i++){
            for (int j = 0; j < cols; j++){
                int id = cols*i+j;
                if(i < rows-1){
                    edges.add(new int[]{id,id+cols,Math.abs(heights[i][j]-heights[i+1][j])});
                }
                if(j < cols-1){
                    edges.add(new int[]{id,id+1,Math.abs(heights[i][j]-heights[i][j+1])});

                }
            }
        }
        Collections.sort(edges, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2]-o2[2];
            }
        });
        int ans = 0;
        UnionFind unionFind = new UnionFind(cols*rows);
        for(int i = 0 ; i < edges.size(); i++){
            int[] edge = edges.get(i);
            int x = edge[0];
            int y = edge[1];
            int w = edge[2];
            // 目的就是把不一样的合并在一起，这才是并查集的作用，伟大之处
            if(unionFind.find(x)!=unionFind.find(y)){
                unionFind.union(x,y);
            }
            if(unionFind.find(0) == unionFind.find(rows*cols-1)){
                ans = w;
                break;
            }
        }
        return ans;
    }
}
class UnionFind{
    // 构造函数，路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。
    int[] f;
    public UnionFind(int n){
        f = new int[n];
        for(int i = 0;i < n; i++){
            f[i] = i;
        }
    }
    // 查，找到根节点，也就是这个集合的老大
    public int find(int x){
        if(f[x] != x){
            f[x] = find(f[x]);
        }
        return f[x];
    }
    // 并，在根节点之间连边
    public void union(int x,int y){
        if(find(x) != find(y)){
            f[find(x)] = f[find(y)];
        }
    }
}